1. Field of the Invention
This invention relates to computer data storage and server systems, and more particularly to digital video/audio storage and playback systems supporting multiple continuous media streams.
2. Description of the Relevant Art
Multimedia or video server systems are used in a variety of applications for the storage and playback of video, audio or other multimedia data streams. For example, multimedia servers may be used for broadcast, cable or satellite solutions to distribute multimedia information to clients or consumers. Professional broadcasters and associated service providers, such as networks and affiliates or cable providers, may employ digital video servers to support high bandwidth multimedia broadcast applications including multi-channel program playout, ad insertion, and digital content management. Other applications for multimedia server systems may include computer-based training in which multimedia training materials or lectures may be stored on the server system accessed by students over a network or the internet.
Video archiving, browsing and retrieval is another multimedia server application. Various movies may be stored by the server and distributed to users upon request. Video-on-demand or video delivery systems may enable a plurality of users or viewers to selectively watch movies or other audio/video sequences which are stored on one or more video servers or media servers. The video servers may be connected through data transfer channels, such as a broadcast cable system, satellite broadcast system or the internet, to the plurality of users or subscribers. The video servers may store a plurality of movies or other audio/video sequences, and each user can select one or more movies from the video servers for viewing. Each user may include a television or other viewing device, as well as associated decoding logic, for selecting and viewing desired movies. When a user selects a movie, the selected movie may be transferred on one of the data transfer channels to the viewing device of the respective user. Multimedia servers are also found in webcasting applications in which entertainment may be multicast on the internet to different subscribers. Multimedia servers are found in numerous other applications as well.
To meet the demands of many different applications and users, it is desirable for a multimedia server system to provide flexibility and extensibility. Two important requirements for a multimedia server system are storage space and file system bandwidth. Multimedia data, such as full-motion digital video, requires a large amount of storage and data transfer bandwidth. Thus, multimedia systems use various types of video compression algorithms to reduce the amount of necessary storage and data transfer bandwidth. In general, different video compression methods exist for still graphic images and for full-motion video. Video compression methods for still graphic images or single video frames may be intraframe compression methods, and compression methods for motion video may be interframe compression methods.
Examples of video data compression for still graphic images are RLE (Run-Length Encoding) and JPEG (Joint Photographic Experts Group) compression. Although JPEG compression was originally designed for the compression of still images rather than video, JPEG compression is used in some motion video applications. Most video compression algorithms are designed to compress full motion video. Examples of video compression techniques are MPEG (Moving Pictures Experts Group), MPEG-2, DVI (Digital Video Interactive) and Indeo, among others.
Even with the use of compression techniques, multimedia applications may still require extremely large amounts of storage. For example, two hours of video encoded at 1 Mb per second may require roughly one gigabyte (1 GB) of storage. A system supporting numerous different content may require up to several terabytes (TB) of storage. The server system must also be able to provide enough bandwidth for the various users to access selected multimedia content without overloading the storage system. For example, to support 100 simultaneous subscribers viewing multimedia content encoded at 1 Mb per second, a server may need to support a bandwidth in excess of 100 Mb per second when allowing for overhead. If enough bandwidth is not available, then some requests may have to be denied, or the play quality may suffer (video may run too slowly or may appear xe2x80x9cjerkyxe2x80x9d). To meet such storage and bandwidth needs, a multimedia server may utilize one or more RAID (Redundant Array of Inexpensive Drives) storage systems. In a RAID system, for a given multimedia file, blocks of multimedia data may be stored across multiple hard disk units. The blocks may be read out or transferred to the communication network and transmitted or broadcast to the user or users. At the receiving end the blocks may be decoded for user viewing on a display device.
The disks of each hard disk unit may also be considered as being divided into zones. Since they are physically larger, tracks in zones at the outer disk contain more sectors than tracks in zones near the rotational axis of the disk. Therefore, assuming the disks rotate with a constant velocity, the data bandwidth available from the outer most zones is greater than the data bandwidth available from the innermost zones. Even with modem hard disk drives, there can be a 2-1 variation between worst case and average case disk transfer bandwidth due to sectors/track variations between outer and inner zones.
Many multimedia applications require continuous media streams in which data streams must be delivered at a specified and possibly time-varying data rates and with a specified uniformity of that delivery rate. In some cases, the uniformity of the delivery rate may be adversely affected by the algorithm used to satisfy disk access requests. The use of a xe2x80x9cfirst-come, first-servedxe2x80x9d disk access algorithm may not always be the most efficient way to satisfy disk requests, as motion of the read-write head (used to access information from the disk) may be less than optimal. Some optimization of head motion may be realized through the use of algorithms that re-order the disk requests. In such re-ordering algorithms, disk requests may be satisfied in an order different from the order in which they were made. One such re-ordering algorithm is known as an xe2x80x9celevatorxe2x80x9d algorithm. In one typical elevator algorithm, the head of the disk storage system sweeps from the outer disk to the inner disk, satisfying and queued disk request along the way, and then reversing direction. While this algorithm may allow for more efficient motion of the read-write head, highly non-uniform access times may still be present, as newly arriving requests may be satisfied prior to previously queued requests. A large number of newly arriving requests may cause long delays in satisfying previously queued requests.
Non-uniform disk access times may be detrimental to many applications, particularly multimedia applications. For example, video playback from a disk storage system may appear erratic when disk access times are non-uniform. Audio playback may be affected in a similar manner. As such, the quality of a multimedia presentation accessed from a disk storage system with non-uniform access times may suffer.
The problems outlined above may in large part be solved by a system and method of bounded disk request reordering in accordance with the present invention. In one embodiment, disk access requests may be performed during traversals of a disk head across a disk. Each traversal may have a specified direction of motion. A plurality of disk accesses may be performed during a disk head traversal. In some cases, disk accesses may be performed in an order different from the order in which the original disk access requests were received. The overall number of disk access requests for a given disk head traversal may be limited to a maximum number N. By limiting the number of disk requests for each traversal, a bound may effectively be placed on the amount of time it takes to satisfy any single disk request, despite any reordering. Disk head motion may be optimized as well.
In a further embodiment, a disk storage system maintains a list of disk head traverses, known as a traversal list. Each traverse includes several components. The first component of a traverse is a variable for the direction of disk head motion for a given traverse, and may be given a value of xe2x80x9clow-to-highxe2x80x9d or xe2x80x9chigh-to-lowxe2x80x9d. In effect, this variable determines whether a given traverse will read from the outer portion of the disk to the inner portion, or vice versa. The second component of the traverse is an ordered list of disk access requests (the disk request list) which are to be satisfied during the given traverse. The third component of a traverse is a variable indicating the number of disk requests in the disk request list. This variable is bounded to a maximum value (xe2x80x9cNxe2x80x9d) in order to limit the number of disk requests that may be satisfied for a given traverse. A fourth component of a traverse is the Boolean variable xe2x80x9cActivexe2x80x9d. The active variable may be set to a value of false prior to conducting the traverse, and may become true when the traverse is in effect. The final component of a traverse is the current disk block address, or the disk address at which the disk head is located at a given instant in time. Since the direction of motion of the disk head alternates with each new traversal, the number of traverses in the traversal list may be constrained to be even.
The system of one embodiment may perform two algorithms, a queuing algorithm for queuing incoming disk requests, and an execution algorithm for satisfying the queued requests. The queuing algorithm performs the function of placing a newly arrived disk request into a traverse of the traversal list. The newly arrived request may be placed into the disk request list of an active traverse (active=true) or a pending traverse (active=false). The execution algorithm carries out the queued requests of each traverse of the traversal list.
The structure of the algorithms may allow for optimization of disk head motion and more uniform disk access times, despite any reordering. Since the number of disk requests for a given traverse is bounded by a maximum value (xe2x80x9cNxe2x80x9d), the amount of time to satisfy a given disk request may be bounded as well. In effect, the system utilizes an elevator algorithm with a bounded maximum delay for a given disk request.
Thus, in various embodiments, the system and method of bounded disk request reordering may allow disk requests to be reordered and satisfied within specified bounds. This may result in an optimization of disk head motion, and furthermore, allow for more uniform disk access times. The uniformity of disk access times may make the system more suitable for certain applications in which a relatively steady data stream is required. As such, the system may be particularly suited for use with various multimedia applications.